package addtwonumbersii445

// 实现 两数相加 II https://leetcode.cn/problems/add-two-numbers-ii/
// 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
// -----------
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
// 思路：
// 1. 先遍历链表 l1, d得到其长度 n1
// 2. 再遍历链表 l2, d得到其长度 n2
// 3. 计算出两个链表的长度差 diff = n1 - n2
// 4. 如果 diff > 0, 则将 l1 向后移动 diff 位
// 5. 如果 diff < 0, 则将 l2 向后移动 -diff 位
// 6. 然后同时遍历两个链表，进行相加，注意进位的处理。
// 7. 最后将结果存入一个新的链表中，返回这个链表。
// 8. 注意链表的头节点需要特殊处理。
// 9. 时间复杂度 O(max(m, n))，空间复杂度 O(max(m, n))，其中 m 和 n 分别是链表 l1 和 l2 的长度。
// 10. 注意：这里的链表是单向链表，所以我们需要使用栈来存储链表的值。
func addTwoNumbersV2(l1 *ListNode, l2 *ListNode) *ListNode {
	n1, n2 := 0, 0
	l1_init, l2_init := l1, l2 // 保存初始值
	// 遍历链表 l1 和 l2，分别得到它们的长度 n1 和 n2
	for l1_init != nil {
		n1++
		l1_init = l1_init.Next
	}
	for l2_init != nil {
		n2++
		l2_init = l2_init.Next
	}

	// 计算出两个链表的长度差 diff = n1 - n2
	// 调整 l1 和 l2 的位置，使得它们的长度相同
	diff := n1 - n2
	if diff > 0 {
		for diff > 0 {
			l1 = l1.Next
			diff--
		}
	} else if diff < 0 {
		for diff < 0 {
			l2 = l2.Next
			diff++
		}
	}

	dummy := &ListNode{}
	carry := 0

	for l1 != nil || l2 != nil || carry > 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		carry = sum / 10
		node := &ListNode{Val: sum % 10}
		node.Next = dummy.Next
		dummy.Next = node
	}

	return dummy.Next
}
